package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/11 16:01
 * https://leetcode-cn.com/problems/ones-and-zeroes/
 */
public class Title474 {

    /**
     * dp[i][j]表示背包容量为i,j时，存放物品的个数最多
     * 递推公式：dp[i][j] = Math.max(dp[i][j],dp[i- nums[i]][j-nums[j]] +1)
     * 初始化：dp[0][0] = 0;
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        //初始化
        dp[0][0] = 0;
        for(int i = 0; i < strs.length; i++){
            int zero = 0;
            int one = 0;
            String s = strs[i];
            for(int j = 0; j < s.length(); j++){
                if(s.charAt(j)=='0'){
                    zero++;
                }else{
                    one++;
                }
            }
            for (int j = m; j >= zero; j--) {
                for (int k = n; k >= one ; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - zero][k - one] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public static int findMaxForm1(String[] strs, int m, int n) {
        //dp[i][j]表示装满i个0，j个1的背包最多的物品个数
        int[][] dp = new int[m + 1][n + 1];
        int[][] arr = new int[strs.length][2];
        for(int i = 0; i < strs.length; i++){
            int one = 0, zero = 0;
            for(int j = 0; j < strs[i].length(); j++){
                if(strs[i].charAt(j) == '1'){
                    one++;
                }else{
                    zero++;
                }
            }
            arr[i][0] = one;
            arr[i][1] = zero;
        }
        for(int i = 0; i < arr.length; i++){
            for(int j = m; j >= arr[i][1]; j--){
                for(int k = n; k >= arr[i][0]; k--){
                    dp[j][k] = Math.max(dp[j][k], dp[j - arr[i][1]][k - arr[i][0]] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String[] arr = {"10","0001","111001","1","0"};
        findMaxForm(arr, 5,3);
    }
}
